package merisis.experiments.gcs;

import static java.lang.String.format;

public class GCSearch5 extends AbstractGuessComplemetSearch {

	/**
	 * <table border="1">
	 * <tr>
	 * <td> x
	 * <td> 654
	 * <td> 321
	 * <td> 0
	 * <td></tr>
	 * <tr>
	 * <td>--</td>
	 * <td>condition
	 * <td>fact
	 * <td>result of guest</td>
	 * </tr>
	 * </table>
	 * 
	 * 1 - btm, 2 - tbm, 3 - mbt, 4 - mbt, 5 - bmt, 6 - tmb <br>
	 * <tr>
	 * <td>0-bit</td>
	 * <td>0 - missed, 1 - hit </td>
	 * <tr>
	 * <td>0 - empty, 1 - b, 2 - t, 3 - m, 4 - min{|m-t|,|m-b|}
	 */
	private final static byte[] DECISION_TBL = new byte[] { 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 2, 3, 1, 3, 1, 3, 2, 2,
			2, 2, 0, 0, 0, 0, 1, 3, 1, 3, 2, 3, 2, 3, 1, 1, 1, 1, 0, 0, 0, 0,
			1, 3, 1, 3, 2, 3, 2, 3, 1, 1, 1, 1, 0, 0, 0, 0, 2, 3, 2, 3, 1, 3,
			1, 3, 2, 2, 2, 2, 0, 0, 0, 0, 4, 3, 4, 3, 4, 3, 4, 3, 4, 4, 4, 4,
			0, 0, 0, 0, 4, 3, 4, 3, 4, 3, 4, 3, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };

	public long searchAlgoritm(long start, long end, long key) {

		long entrance = (start + end) >> 1;

		long high = end;
		long low = start;
		long topVal;
		long btmVal;
		long entranceVal = access(entrance);
		if (key < entranceVal) {

			low = start;
			btmVal = access(low);
			high = entrance;
			topVal = entranceVal;
		} else if (key > entranceVal) {

			low = entrance;
			btmVal = entranceVal;
			high = end;
			topVal = access(high);
		} else {
			return entrance;
		}

		byte style0 = 1;
		byte experience = 1; // 0 - hit, 1 - missed
		while (low <= high) {

			// jumping function
			long didx = high - low;
			long jump_b;
			long jump_t;
			long jump_m;

			long scope = topVal - btmVal;

			jump_b = low + (int) ((((double) (key - btmVal)) * didx) / scope);
			jump_t = high - (int) ((((double) (topVal - key)) * didx) / scope);
			jump_m = (high + low) >> 1;

			byte style;
			if (jump_b < jump_m) {
				if (jump_t < jump_m) {
					if (jump_b < jump_t) {
						style = 1; // (b t m)
					} else {
						style = 2; // (t b m)
					}
				} else {
					style = 5; // (b m t)
				}
			} else {
				if (jump_t > jump_m) {
					if (jump_b < jump_t) {
						style = 3; // (m b t)
					} else {
						style = 4; // (m b t)
					}
				} else {
					style = 6; // (t m b)
				}
			}

			long[] opts = new long[] { 0, jump_b, jump_t, jump_m };

			int sig = (style << 4) | (style0 << 1) | experience;

			long jump;
			byte opt = DECISION_TBL[(byte) sig];
			if (opt == 1) {
				jump = jump_b;
			} else if (opt == 2) {
				jump = jump_t;
			} else if (opt == 3) {
				jump = jump_m;
			} else if (opt == 4) {
				if (jump_b < jump_t) {
					long d0 = jump_m - jump_b;
					long d1 = jump_t - jump_m;
					if (d0 < 0 || d1 < 0)
						throw new IllegalStateException();

					if (d0 < d1)
						jump = jump_b;
					else
						jump = jump_t;
				} else {
					long d0 = jump_b - jump_m;
					long d1 = jump_m - jump_t;

					if (d0 < 0 || d1 < 0)
						throw new IllegalStateException();

					if (d0 < d1)
						jump = jump_b;
					else
						jump = jump_t;
				}
			} else if (opt == 0)
				jump = jump_m;
			else
				throw new IllegalStateException("unkonw: " + opt);

//			System.out.println(format(
//					"w[%d,%d] s%d=>s%d(btm|%d,%d,%d) ex=%d |> jp=%d, op=%d",
//					low, high, style0, style, jump_b, jump_t, jump_m,
//					experience, jump, opt));

			long jumpVal = access(jump);

			experience = 1;
			if (key > jumpVal) {

				low = jump;
				btmVal = jumpVal;
				if (style == 3 || style == 4) {
					experience = 0;
				}
			} else if (key < jumpVal) {

				if (high == jump) {
					return -low;
				}
				high = jump;
				topVal = jumpVal;

				if (style == 1 || style == 2) {
					experience = 0;
				}
			} else
				return jump; // key found

			style0 = style;

		}

		return -(low + 1); // key not found.
	}
}
